Game AI
A Finite State Machine (FSM) is a rigidly formalized device used by mathematicians to solve problems. The most famous FSM is the Turing machine.
A finite state machine is a device, or a model of a device, which has a finite number of states it can be in at any given time and can operate on input to either make transitions from one state to another or to cause an output or action to take place. A finite state machine can only be in one state at any moment in time.
The idea is to decompose an object's behavior into easily manageable chunks or states.
(Programming Game AI by Example by Mat Buckland, 2005. Page 44)
Fuzzy logic is used in fuzzy state machines to make the resulting actions somewhat less predictable and to reduce the burden of having to enumerate huge numbers of if-then rules. Rather than have a rule that states if distance == 10 and health == 100 then attack as in a finite state machine, fuzzy logic allows rules with less precise conditions like if close and health then attack aggressively.
(AI for Game Developers by David M. Bourg and Glenn Seeman, 2004. Page 26)
Pros
- Quick and simple to code
- Easy to debug, since the behavior is broken into manageable chunks
- Little computational overhead - no real processing beyond if-this-then-that
- Intuitive - it's human nature to think about things in states
- Flexible - it's simple to expand the scope of an agent's behavior by adding new states and rules
(Programming Game AI by Example by Mat Buckland, 2005. Page 43-44)
Implement
Use if-then statements or switch statements.
* [e](/view/E)num StateType{[Run](/view/Run)Away, Patrol, Attack};
* void Agent::[Update](/view/Update)State(StateType CurrentState)
* {
* * switch(CurrentState)
* * {
* * * case state_RunAway:
* * * * [E](/view/E)vadeEnemy();
* * * * if (Safe())
* * * * * {
* * * * * * ChangeState(state_Patrol);
* * * * * }
* * * * * break;
*
* * * case state_Patrol:
* * * * FollowPatrolPath();
* * * * if (Threatened())
* * * * * {
* * * * * * if (StrongerThanEnemy())
* * * * * * * {
* * * * * * * * ChangeState(state_Attack);
* * * * * * * }
* * * * * * * [e](/view/E)lse
* * * * * * * {
* * * * * * * * ChangeState(state_Runaway):
* * * * * * * }
* * * * * }
* * * * * break;
*
* * * case state_Attack:
* * * * if (WeakerThanEnemy())
* * * * * {
* * * * * * ChangeState(state_RunAway);
* * * * * }
* * * * * [e](/view/E)lse
* * * * * {
* * * * * * BashEnemyOverHead();
* * * * * }
* * * * * break;
* * }
* }
(Programming Game AI by Example by Mat Buckland, 2005. Page 45-46)
Cons to if/then/switch
- Spaghetti for anything more complicated than this
- Difficult to debug
- Inflexible and difficult to extend beyond the scope of its original design
- Difficult to implement actions when it's initially entered or exited a state (scream AHHH when entering state_RunAway).
- Overall weaker choice than the State Transition Table
(Programming Game AI by Example by Mat Buckland, 2005. Page 46-47)
Examples
- Light-switch - two states: on and off. Transitions between states are made by the input of your finger. Flicking up makes the transition from off to on; an flicking down makes the transition from on to off. In the on state, electricity is allowed to flow through the switch and light up your room via the filament in a light-bulb. (Switches are reversed in Europe and other places.)
- Pac-Man's ghosts - The Evade state is the same for all ghosts. Each ghost has its own Chase state. The input of the player eating one of the power pills is the condition for the transition from Chase to Evade. The input of a timer running down is the condition for the transition from Evade to Chase.
- Quake-style bots - They have states such as FindArmor, FindHealth, SeekCover, and RunAway. Even the weapons have their own mini finite state machines. A rocket may implement states such as Move, TouchObject, and Die.
- Players in sports simulations - states such as Strike, Dribble, ChaseBall, and MarkPlayer. Teams themselves are often implemented as FSMs with states like KickOff, Defend, or WalkOutOnField.
- NPCs in RTSs have states like MoveToPosition, Patrol, and FollowPath.
(Programming Game AI by Example by Mat Buckland, 2005. Page 44-45)